package com.atcumt.Carl.Stack;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

// 队列
public class Stack02 {

    /**
     * 滑动窗口的最大值
     * 单调队列：保证进入滑动窗口的元素小于队尾元素即可
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n < k || k == 0 || nums == null) {
            return new int[0];
        }

        int[] res = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {

            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);

            // 当队头元素已经在滑动窗口外，移除队头元素
            if (deque.getFirst() <= i - k) {
                deque.removeFirst();
            }
            // 当 i 大于等于 k-1 时，单调递减队头就是滑动窗口的最大值
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.getFirst()];
            }
        }
        return res;
    }

    /* 
     * 无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        int start = 0;
        Set<Character> hash = new HashSet<>();
        
        for (int end = 0; end < s.length(); end++) {
            
            //【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】

            //【4、如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题】
            // 如果当前窗口不合法时, 用一个 while 去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            while (hash.contains(s.charAt(end))) {
                hash.remove(s.charAt(start));
                start++;
            }
            hash.add(s.charAt(end));
            maxLen = Math.max(maxLen, end - start + 1);
        }
        return maxLen;
    }
}
